// dynamic SeqList 动态顺序表
// 实际运用更加灵活

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>



typedef int SQDataType;
typedef struct SeqList
{
    SQDataType* data; // 数组的指针实现
    int size; // 有效数据的个数
    int capacity; // 数组容量
}SeqList;

void SeqListInit(SeqList* psl);
void SeqListDestroy(SeqList* psl);
void SeqListCheckCapacity(SeqList* psl);

void SeqListPushBack(SeqList* psl, SQDataType val);
void SeqListPushFront(SeqList* psl, SQDataType val);
void SeqListPopBack(SeqList* psl);
void SeqListPopFront(SeqList* psl);
void SeqListInsert(SeqList* psl, int pos, SQDataType val);
void SeqListErase(SeqList* psl, int pos);

int SeqListFind(SeqList* psl, SQDataType val);
void SeqListPrint(SeqList* psl);
void SeqListInit(SeqList* psl)
{
    psl->data = NULL;
    psl->size = 0;
    psl->capacity = 0;
}

void SeqListDestroy(SeqList* psl)
{
    free(psl->data);
    psl->data = NULL;
    psl->capacity = psl->size = 0;
}

void SeqListCheckCapacity(SeqList* psl)
{
    if (psl->size == psl->capacity){
        int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        SQDataType* tmp = (SQDataType*)realloc(psl->data, psl->capacity * 2 * sizeof(SQDataType));
        if (tmp == NULL){
            printf("realloc fail\n");
            exit(-1);
        }
        else {
            psl->data = tmp;
            psl->capacity = newCapacity;
        }
    }
}

void SeqListPushBack(SeqList* psl, SQDataType val)
{
    SeqListCheckCapacity(psl);
    psl->data[psl->size] = val;
    psl->size++;
}

void SeqListPushFront(SeqList* psl, SQDataType val)
{
    SeqListCheckCapacity(psl);

    int end = psl->size - 1;
    while (end >= 0){
        psl->data[end + 1] = psl->data[end];
        end--;
    }
    psl->data[0] = val;
    psl->size++;
}

void SeqListPopBack(SeqList* psl)
{
    assert(psl->size > 0);

    psl->size--;
}

void SeqListPopFront(SeqList* psl)
{
    assert(psl->size);

    int start = 1;
    while (start < psl->size){
        psl->data[start] = psl->data[start - 1];
        start++;
    }
    psl->size++;
}

void SeqListInsert(SeqList* psl, int pos, SQDataType val)
{
    assert(pos <= psl->size); // pos指的是下标，实际上是第三个位置
    SeqListCheckCapacity(psl);

    int end = psl->size - 1;
    while (end >= pos){
        psl->data[end + 1] = psl->data[end];
        end--;
    }
    psl->data[pos] = val;
    psl->size++;
}

void SeqListErase(SeqList* psl, int pos)
{
    assert(pos < psl->size);

    int start = pos + 1;
    while (start < psl->size){
        psl->data[start - 1] = psl->data[start];
        start++;
    }
    psl->size--;
}

int SeqListFind(SeqList* psl, SQDataType val)
{
    for (int i = 0 ; i < psl->size ; i++){
        if (psl->data[i] == val){
            return i;
        }
    }

    return -1;
}

// 修改
void SeqListModify(SeqList* psl, int pos, SQDataType val)
{
    assert(pos < psl->size);

    psl->data[pos] = val;
}

void SeqListPrint(SeqList* psl)
{
    for (int i = 0 ; i < psl->size ; i++){
        printf("%d ", psl->data[i]);
    }
    putchar('\n');
}

int main(void)
{
    // 初始化
    SeqList sl;
    SeqListInit(&sl);

    // 尾插
    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 5);
    SeqListPrint(&sl);

    // 头插
    SeqListPushFront(&sl, 2);
    SeqListPrint(&sl);

    // 尾删
    SeqListPopBack(&sl);
    SeqListPrint(&sl);

    // 头删
    SeqListPopFront(&sl);
    SeqListPrint(&sl);

    // 插入
    SeqListInsert(&sl, 2, 20);
    SeqListPrint(&sl);

    // 删除
    SeqListErase(&sl, 2);
    SeqListPrint(&sl);

    // 销毁
    SeqListDestroy(&sl);

    return 0;
}







